{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Insert Greatest Common Divisors in Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #linked-list #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #链表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: insertGreatestCommonDivisors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在链表中插入最大公约数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表的头&nbsp;<code>head</code>&nbsp;，每个结点包含一个整数值。</p>\n",
    "\n",
    "<p>在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 <strong>最大公约数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回插入之后的链表。</p>\n",
    "\n",
    "<p>两个数的 <strong>最大公约数</strong>&nbsp;是可以被两个数字整除的最大正整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/18/ex1_copy.png\" style=\"width: 641px; height: 181px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>head = [18,6,10,3]\n",
    "<b>输出：</b>[18,6,6,2,10,1,3]\n",
    "<b>解释：</b>第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。\n",
    "- 18 和 6 的最大公约数为 6 ，插入第一和第二个结点之间。\n",
    "- 6 和 10 的最大公约数为 2 ，插入第二和第三个结点之间。\n",
    "- 10 和 3 的最大公约数为 1 ，插入第三和第四个结点之间。\n",
    "所有相邻结点之间都插入完毕，返回链表。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/18/ex2_copy1.png\" style=\"width: 51px; height: 191px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>head = [7]\n",
    "<strong>输出：</strong>[7]\n",
    "<b>解释：</b>第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。\n",
    "没有相邻结点，所以返回初始链表。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中结点数目在&nbsp;<code>[1, 5000]</code> 之间。</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [insert-greatest-common-divisors-in-linked-list](https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [insert-greatest-common-divisors-in-linked-list](https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[18,6,10,3]', '[7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def maxdiv(x, y):\n",
    "            res = 1\n",
    "            minvalue = min(x,y)\n",
    "            for i in range(1, minvalue+1):\n",
    "                if x % i == 0 and y % i == 0:\n",
    "                    res = i\n",
    "            return res\n",
    "        dump = head\n",
    "        while head.next:\n",
    "            pre, cur = head, head.next\n",
    "            mid = ListNode(maxdiv(pre.val, cur.val))\n",
    "            pre.next = mid\n",
    "            mid.next = cur\n",
    "            head = cur\n",
    "        return dump"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        phead = head\n",
    "        left = phead\n",
    "        right = left.next\n",
    "        while right:\n",
    "            node1 = ListNode(self.greatestCommonDivisors(left.val,right.val))\n",
    "            node1.next = right\n",
    "            left.next = node1\n",
    "            left = right\n",
    "            right = left.next\n",
    "        return phead\n",
    "\n",
    "\n",
    "    # 辗转相除求最大公约数\n",
    "    def greatestCommonDivisors(self,left,right):\n",
    "        while left != 0:\n",
    "            new = right % left\n",
    "\n",
    "            right = left\n",
    "\n",
    "            left = new\n",
    "\n",
    "        return right\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "        cur = head\n",
    "        if cur.next : \n",
    "            while cur.next:\n",
    "                tmp = ListNode(val=gcd(cur.val,cur.next.val))\n",
    "                tmp.next = cur.next\n",
    "                cur.next = tmp\n",
    "                cur = tmp.next\n",
    "        return head \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head.next:\n",
    "            return head\n",
    "        node = head\n",
    "        bef = 1\n",
    "        while node.next:\n",
    "           bef = self.maxDivide(node.val, node.next.val, bef)\n",
    "           tmp = node.next\n",
    "           mid = ListNode(bef, tmp)\n",
    "           node.next = mid\n",
    "           node = tmp\n",
    "        return head        \n",
    "\n",
    "    def maxDivide(self, val1, val2, bef):\n",
    "        if val1 == val2:\n",
    "            return val2\n",
    "        if val1 < val2:\n",
    "            val1, val2 = val2, val1\n",
    "\n",
    "        #val1>=val2\n",
    "        if val1%val2 == 0:\n",
    "            return val2\n",
    "        res = 1\n",
    "        if val1%bef == 0 and val2%bef == 0:\n",
    "            res = bef\n",
    "        cur = res + 1\n",
    "        while cur<val2:\n",
    "            if val1%cur == 0 and val2%cur == 0:\n",
    "                res = cur\n",
    "            cur += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def maxcom(a, b):\n",
    "            v = min(a, b)\n",
    "            for vi in range(v, 0, -1):\n",
    "                if a%vi == 0 and b%vi == 0:\n",
    "                    return vi\n",
    "            return 1\n",
    "        \n",
    "        ins = []\n",
    "        cur = head\n",
    "        while cur and cur.next:\n",
    "            a, b = cur.val, cur.next.val\n",
    "            ins = maxcom(a, b)\n",
    "            remains = cur.next\n",
    "            cur.next = ListNode(ins, remains)\n",
    "            cur = remains\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        pre = head\n",
    "        nxt = head.next\n",
    "\n",
    "        while nxt:\n",
    "            val = gcd(pre.val, nxt.val)\n",
    "            node = ListNode(val)\n",
    "            pre.next = node\n",
    "            node.next = nxt\n",
    "            pre = nxt\n",
    "            nxt = nxt.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def gcd(a,b):\n",
    "            while b!=0:\n",
    "                a,b=b,a%b\n",
    "            return a\n",
    "        hummy=head\n",
    "        while hummy.next:\n",
    "            hummy.next=ListNode(gcd(hummy.val,hummy.next.val),hummy.next)\n",
    "            hummy=hummy.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur.next is not None:\n",
    "            next = cur.next\n",
    "            cur.next = None\n",
    "            node = ListNode(gcd(cur.val, next.val), next)\n",
    "            cur.next = node\n",
    "            cur = next\n",
    "        return head\n",
    "\n",
    "    # def gcd(self, a, b):\n",
    "    #     return b == 0 if a else gcd(self, b, a % b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        current = head\n",
    "        while current.next:\n",
    "            a = current.val\n",
    "            nextNode = current.next\n",
    "            b = nextNode.val\n",
    "            gcd = self.getGreatestCommonDivisors(a, b)\n",
    "            newNode = ListNode()\n",
    "            newNode.val = gcd\n",
    "            current.next = newNode\n",
    "            newNode.next = nextNode\n",
    "            current = nextNode\n",
    "        return head\n",
    "\n",
    "    def getGreatestCommonDivisors(self, a, b):\n",
    "        while a % b != 0:\n",
    "            a, b = b, a % b\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import math\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # if head is None or head.next is None:\n",
    "        #     return head\n",
    "\n",
    "        dum = cur = head\n",
    "        while cur and cur.next:\n",
    "            num = math.gcd(cur.val, cur.next.val)\n",
    "            num = ListNode(num)\n",
    "            temp = cur.next\n",
    "            cur.next = num\n",
    "            num.next = temp\n",
    "            cur = temp\n",
    "\n",
    "        return dum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        a = head\n",
    "        b = a.next\n",
    "        while b:\n",
    "            c = ListNode(math.gcd(a.val, b.val))\n",
    "            a.next = c\n",
    "            c.next = b\n",
    "            a = b\n",
    "            b = a.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur=head\n",
    "        while cur.next:\n",
    "            node=ListNode(gcd(cur.val,cur.next.val),cur.next)\n",
    "            cur.next=node\n",
    "            cur=node.next\n",
    "        return head\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        def maxv(v1,v2):\n",
    "            if v1<v2:\n",
    "                v1,v2 = v2,v1\n",
    "            while v1%v2!=0:\n",
    "                v1 = v1-v2\n",
    "                if v1<v2:\n",
    "                    v1,v2 = v2,v1\n",
    "            return min(v1,v2)\n",
    "\n",
    "        \n",
    "        pre, post = head, head.next\n",
    "        while post!=None:\n",
    "            mid = ListNode(maxv(pre.val, post.val))\n",
    "            pre.next = mid\n",
    "            mid.next = post\n",
    "\n",
    "            pre = post\n",
    "            post = pre.next\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur.next != None:\n",
    "            tmp = ListNode(gcd(cur.val, cur.next.val))\n",
    "            tmp.next = cur.next\n",
    "            cur.next = tmp\n",
    "            cur = cur.next.next\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur,ne=head, head.next\n",
    "        while ne:\n",
    "            cur.next = ListNode(self.gcd(cur.val, ne.val), ne)\n",
    "            cur = ne\n",
    "            ne = ne.next\n",
    "        return head\n",
    "    def gcd(self, cur, ne):\n",
    "        maxN=max(cur,ne)\n",
    "        minN=min(cur,ne)\n",
    "        r = maxN%minN\n",
    "        while r!=0:\n",
    "            maxN, minN = minN, r\n",
    "            r = maxN%minN\n",
    "        return minN "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            cur.next = ListNode(gcd(cur.val,cur.next.val),cur.next)\n",
    "            cur = cur.next.next\n",
    "        return head\n",
    "    def gcd(a,b):\n",
    "        while b!=0:\n",
    "            a,b = b,a%b\n",
    "        return abs(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # if not head.next:\n",
    "        #     return head\n",
    "        \n",
    "        def get_gcd(num1, num2):\n",
    "            while num2:\n",
    "                num1, num2 = num2, num1 % num2\n",
    "            return num1\n",
    "\n",
    "        pre = head\n",
    "        now = head.next\n",
    "        while now:\n",
    "            gcd = get_gcd(pre.val, now.val)\n",
    "            pre.next = ListNode(gcd)\n",
    "            pre.next.next = now\n",
    "            pre = now\n",
    "            now = now.next\n",
    "        \n",
    "        return head\n",
    "        \n",
    "\n",
    "       \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            g = gcd(cur.val, cur.next.val)\n",
    "            cur.next = ListNode(g,cur.next)\n",
    "            cur = cur.next.next\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p = head\n",
    "        while p.next:\n",
    "            p1 = ListNode(gcd(p.val,p.next.val))\n",
    "            p1.next, p.next ,p = p.next,p1,p.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur=head\n",
    "        while cur.next:\n",
    "            cur.next=ListNode(math.gcd(cur.val,cur.next.val),cur.next)\n",
    "            cur=cur.next.next\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def helper(a,b):\n",
    "            if not a%b:\n",
    "                return b\n",
    "            else:\n",
    "                return helper(b,a%b)\n",
    "        header=head\n",
    "        p=header\n",
    "        while p.next:\n",
    "            a=p.val\n",
    "            b=p.next.val\n",
    "            node=ListNode(val=helper(a,b))\n",
    "            node.next=p.next\n",
    "            p.next=node\n",
    "            p=node.next\n",
    "        return header\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur and cur.next:\n",
    "            node =ListNode(gcd(cur.val,cur.next.val))\n",
    "            node.next = cur.next\n",
    "            cur.next = node\n",
    "            cur = node.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def f(num1, num2):\n",
    "    if num1 % num2 == 0:\n",
    "        return num2\n",
    "    f(num2,  num1 % num2)\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur.next != None:\n",
    "            tmp = ListNode()\n",
    "            num1 = cur.val\n",
    "            num2 = cur.next.val\n",
    "            while num1 % num2 != 0 :\n",
    "                num1, num2 = num2, num1 % num2\n",
    "            tmp.val = num2\n",
    "            tmp.next = cur.next\n",
    "            cur.next = tmp\n",
    "            cur = cur.next.next\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    import math\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur=head\n",
    "        while cur and cur.next:\n",
    "            new_node=ListNode(math.gcd(cur.val, cur.next.val))\n",
    "            new_node.next=cur.next\n",
    "            cur.next=new_node\n",
    "            cur=new_node.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur and cur.next:\n",
    "            node =ListNode(gcd(cur.val,cur.next.val))\n",
    "            node.next = cur.next\n",
    "            cur.next = node\n",
    "            cur = node.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head.next==None:\n",
    "            return head\n",
    "        pA=head\n",
    "        pB=head.next\n",
    "        def count_maths(self,num1,num2):\n",
    "            if num1<num2:\n",
    "                num1,num2=num2,num1  # 默认num1为较大者\n",
    "            count=1\n",
    "            for i in range(2,num2+1):\n",
    "                if num1%i==0 and num2%i==0:\n",
    "                    count=i\n",
    "            return count\n",
    "        while pB:\n",
    "            p=ListNode()\n",
    "            p.val=count_maths(self,pA.val,pB.val)\n",
    "            p.next=pB\n",
    "            pA.next=p\n",
    "            pA=pB\n",
    "            pB=pB.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "        \n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            if cur and pre:\n",
    "                pre.next = ListNode(gcd(pre.val, cur.val), cur)\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def maxyueshu(self,a,b):\n",
    "        a,b = max(a, b),min(a, b)\n",
    "        while a % b != 0:\n",
    "            tem = a\n",
    "            a = b\n",
    "            b = tem % b\n",
    "        return b\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head.next:return head\n",
    "        pre,res = head,head\n",
    "        head = head.next\n",
    "        while head:\n",
    "            yueshu = ListNode(self.maxyueshu(pre.val,head.val))\n",
    "            yueshu.next = head\n",
    "            pre.next = yueshu   \n",
    "                     \n",
    "            pre = head\n",
    "            head = head.next\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p, q = head, head.next\n",
    "        while q:\n",
    "            p.next = ListNode(gcd(p.val, q.val), q)\n",
    "            p, q = q, q.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def maxyueshu(self,a,b):\n",
    "        a,b = max(a, b),min(a, b)\n",
    "        while a % b != 0:\n",
    "            tem = a\n",
    "            a = b\n",
    "            b = tem % b\n",
    "        return b\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head.next:return head\n",
    "        pre,res = head,head\n",
    "        head = head.next\n",
    "        while head:\n",
    "            yueshu = ListNode(self.maxyueshu(pre.val,head.val))\n",
    "            \n",
    "            pre.next = yueshu   \n",
    "            yueshu.next = head         \n",
    "            pre = head\n",
    "            head = head.next\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def slove(n, m):\n",
    "            if m == 0: return n\n",
    "            return slove(m, n % m)\n",
    "    \n",
    "        def help(p, x):\n",
    "            node = ListNode(x)\n",
    "            node.next = p.next\n",
    "            p.next = node\n",
    "        \n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        \n",
    "        p = head\n",
    "        while p and p.next:\n",
    "            x = slove(p.val, p.next.val)\n",
    "            help(p, x)\n",
    "            p = p.next.next\n",
    "        return head "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def gys(a,b):\n",
    "            maxx = max(a,b)\n",
    "            minn = min(a,b)\n",
    "            c = maxx%minn\n",
    "            while c != 0:\n",
    "                maxx = minn\n",
    "                minn = c\n",
    "                c = maxx % minn\n",
    "            return minn\n",
    "\n",
    "        now,nxt = head,head.next #获取当前节点和下一个节点\n",
    "        while nxt != None: #判断是否到头\n",
    "            c = gys(now.val,nxt.val) #获取最大公约数\n",
    "            num = ListNode(c,nxt) #？？？？这种方式创建的变量是否为局部变量，到时候会回收？？？\n",
    "            now.next = num\n",
    "            now = nxt\n",
    "            nxt = nxt.next\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = head\n",
    "        if not head.next: return head\n",
    "\n",
    "        while head and head.next:\n",
    "            _next = head.next\n",
    "            new = ListNode(val=math.gcd(head.val, _next.val))\n",
    "            head.next = new\n",
    "            new.next = _next\n",
    "            head = _next\n",
    "        \n",
    "        return dummy\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def maxNum(a,b):\n",
    "            num = max(a,b)\n",
    "            rnum = 1\n",
    "            for i in range(1,num+1):\n",
    "                if a % i == 0 and b % i == 0:\n",
    "                    if i > rnum:\n",
    "                        rnum = i\n",
    "            return rnum\n",
    "        if not head or head.next == None:\n",
    "            return head\n",
    "        pre = head\n",
    "        while pre != None and pre.next != None:\n",
    "            a,b = pre.val,pre.next.val\n",
    "            tempNode = ListNode(maxNum(a,b))\n",
    "            tempNode.next = pre.next\n",
    "            pre.next = tempNode\n",
    "            pre = pre.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        h=ListNode(0)\n",
    "        h.next=head\n",
    "        cur=head\n",
    "        \n",
    "        while cur and cur.next:\n",
    "            n=ListNode(math.gcd(cur.val,cur.next.val))\n",
    "            n.next=cur.next\n",
    "            cur.next=n\n",
    "            cur=cur.next.next\n",
    "        \n",
    "        return h.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur_node=head\n",
    "        while(cur_node and cur_node.next):\n",
    "            temp=ListNode(math.gcd(cur_node.val,cur_node.next.val),cur_node.next)\n",
    "            cur_node.next=temp\n",
    "            cur_node=temp.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur=head\n",
    "        while cur.next:\n",
    "            newnode=ListNode(math.gcd(cur.val,cur.next.val),cur.next)\n",
    "            cur.next=newnode\n",
    "            cur=newnode.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur and cur.next:\n",
    "            node =ListNode(gcd(cur.val,cur.next.val))\n",
    "            node.next = cur.next\n",
    "            cur.next = node\n",
    "            cur = node.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            cur.next = ListNode(gcd(cur.val, cur.next.val), cur.next)\n",
    "            cur = cur.next.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p=head\n",
    "        if not p or not p.next:\n",
    "            return head\n",
    "        \n",
    "        while(p.next):\n",
    "            q=p.next\n",
    "            node=ListNode(math.gcd(p.val,q.val), q)\n",
    "            p.next=node\n",
    "            \n",
    "            p=p.next.next\n",
    "        return head\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur_node=head\n",
    "        while(cur_node and cur_node.next):\n",
    "            temp=ListNode(math.gcd(cur_node.val,cur_node.next.val),cur_node.next)\n",
    "            cur_node.next=temp\n",
    "            cur_node=temp.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def common_divisor(self,num_1,num_2):\n",
    "        for i in range(min(num_1,num_2),0,-1):\n",
    "            if num_1%i==0 and num_2%i==0:\n",
    "                return i\n",
    "        return 1\n",
    "\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur_node=head\n",
    "        while(cur_node and cur_node.next):\n",
    "            MCD=self.common_divisor(cur_node.val,cur_node.next.val)\n",
    "            temp=ListNode(MCD,cur_node.next)\n",
    "            cur_node.next=temp\n",
    "            cur_node=temp.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        cur = head\n",
    "        next = cur.next\n",
    "\n",
    "        while next:\n",
    "            node = ListNode(gcd(cur.val, next.val), next)\n",
    "            cur.next = node\n",
    "\n",
    "            cur = next\n",
    "            next = next.next\n",
    "            \n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p=head \n",
    "        while p.next:\n",
    "            x=math.gcd(p.val,p.next.val)\n",
    "            t=p.next\n",
    "            p.next=ListNode(x,t)\n",
    "            p=t\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    def gcd(self, a, b):\n",
    "        return gcd(b, a%b) if b else a\n",
    "\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head.next == None:\n",
    "            return head\n",
    "        curNode = head\n",
    "        while curNode.next:\n",
    "            node = ListNode(self.gcd(curNode.val, curNode.next.val), curNode.next)\n",
    "            curNode.next = node\n",
    "            curNode = node.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur and cur.next:\n",
    "            node =ListNode(gcd(cur.val,cur.next.val))\n",
    "            node.next = cur.next\n",
    "            cur.next = node\n",
    "            cur = node.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def commondivisor(self, num1, num2):\n",
    "        ans = -inf\n",
    "        for i in range(1, min(num1, num2)+1):\n",
    "            if num1 % i == 0 and num2 % i == 0:\n",
    "                if ans < i:\n",
    "                    ans = i\n",
    "        return ans\n",
    "\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head.next: return head\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            nxt = cur.next\n",
    "            new_node = ListNode(self.commondivisor(cur.val, nxt.val))\n",
    "            cur.next = new_node\n",
    "            new_node.next = nxt\n",
    "            cur = nxt\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur and cur.next:\n",
    "            nxt = cur.next\n",
    "            tmp = gcd(cur.val, nxt.val)\n",
    "            cur.next = ListNode(tmp, nxt)\n",
    "            cur = nxt\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        p=head\n",
    "        while p.next:\n",
    "            p.next=ListNode(gcd(p.val,p.next.val),p.next)\n",
    "            p=p.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "#求最大公因数\n",
    "def common_factor(a,b):\n",
    "    res=1\n",
    "    if a==b:\n",
    "        res=a\n",
    "    if a>b:\n",
    "        while b!=0:\n",
    "            t=a%b\n",
    "            a=b\n",
    "            b=t\n",
    "        res=a\n",
    "    if a<b:\n",
    "        while a!=0:\n",
    "            t=b%a\n",
    "            b=a\n",
    "            a=t\n",
    "        res=b\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur=head\n",
    "        while cur.next:\n",
    "            node = ListNode(common_factor(cur.val,cur.next.val),cur.next)\n",
    "            cur.next=node\n",
    "            cur =cur.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def gcd(x,y):\n",
    "            if max(x,y)%min(x,y)==0:\n",
    "                return min(x,y)\n",
    "            return gcd(min(x,y),max(x,y)%min(x,y))\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "        dummy_head=ListNode()\n",
    "        dummy_head.next=head\n",
    "        pre=dummy_head\n",
    "        cur=head\n",
    "        while cur:\n",
    "            pre=cur\n",
    "            cur=cur.next\n",
    "            if cur:\n",
    "                val=gcd(pre.val, cur.val)\n",
    "                pre.next=ListNode(val,next=cur)\n",
    "        return dummy_head.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def common_divisor(self,num_1,num_2):\n",
    "        for i in range(min(num_1,num_2),0,-1):\n",
    "            if num_1%i==0 and num_2%i==0:\n",
    "                return i\n",
    "        return 1\n",
    "\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur_node=head\n",
    "        while(cur_node and cur_node.next):\n",
    "            MCD=self.common_divisor(cur_node.val,cur_node.next.val)\n",
    "            temp=ListNode(MCD,cur_node.next)\n",
    "            cur_node.next=temp\n",
    "            cur_node=temp.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            cur.next = ListNode(gcd(cur.val,cur.next.val),cur.next)\n",
    "            cur = cur.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        x, y = head, head.next\n",
    "        while y:\n",
    "            a, b = max(x.val, y.val), min(x.val, y.val)\n",
    "            while b:\n",
    "                a, b = b, a%b\n",
    "            z = ListNode(a)\n",
    "            x.next, z.next = z, y\n",
    "            x, y = y, y.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            cur.next = ListNode(gcd(cur.val, cur.next.val), cur.next)\n",
    "            cur = cur.next.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p = head\n",
    "        while p and p.next:\n",
    "            p1 = ListNode(gcd(p.val, p.next.val))\n",
    "            p1.next, p.next, p = p.next, p1, p.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def gcd(a, b):\n",
    "            while a != b:\n",
    "                if a > b:\n",
    "                    a -= b\n",
    "                elif a < b:\n",
    "                    b -= a\n",
    "            return b\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            cur.next = ListNode(gcd(cur.val, cur.next.val), cur.next)\n",
    "            cur = cur.next.next\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # def gcd(a, b):\n",
    "        #     if not b:\n",
    "        #         return a\n",
    "        #     if b > a:\n",
    "        #         return gcd(b, a)\n",
    "        #     return gcd(b, a%b)\n",
    "        \n",
    "        # dummy = ListNode(next=head)\n",
    "        # p = head \n",
    "        # while p.next:\n",
    "        #     nxt = p.next\n",
    "        #     p.next = ListNode(gcd(p.val, nxt.val))\n",
    "        #     p.next.next = nxt \n",
    "        #     p = nxt \n",
    "        # return dummy.next\n",
    "\n",
    "        # ---------------------------------\n",
    "        def gcd(a, b):\n",
    "            if not b:\n",
    "                return a\n",
    "            if b > a:\n",
    "                return gcd(b, a)\n",
    "            return gcd(b, a%b)\n",
    "        \n",
    "        p = head \n",
    "        while p.next:\n",
    "            p.next = ListNode(val=gcd(p.val, p.next.val), next=p.next)            \n",
    "            p = p.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        #= math.gcd(num1, num2)\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        def insert_gcd_node(head):\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "\n",
    "   \n",
    "        def insert_after_node(node, val):\n",
    "            new_node = ListNode(val)\n",
    "            new_node.next = node.next\n",
    "            node.next = new_node\n",
    "\n",
    "        current = head\n",
    "        while current and current.next:\n",
    "            gcd_value = gcd(current.val, current.next.val)\n",
    "            insert_after_node(current, gcd_value)\n",
    "            current = current.next.next  # Skip to the node after the inserted one\n",
    "\n",
    "        return head\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        node = head\n",
    "        while node.next:\n",
    "            val = math.gcd(node.val, node.next.val)\n",
    "            newnode = ListNode(val, node.next)\n",
    "            node.next = newnode\n",
    "            node=newnode.next\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    cache = {}\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        Solution.cache = {}\n",
    "        if head.next == None :\n",
    "            return head\n",
    "        p1,p2 = head,head.next\n",
    "        while p2 != None :\n",
    "            t1,t2 = p1,p2\n",
    "            p1,p2 = p2,p2.next\n",
    "\n",
    "            new_v = self.get_num(t1.val,t2.val)\n",
    "            p = ListNode(new_v)\n",
    "            t1.next = p\n",
    "            p.next = t2\n",
    "\n",
    "            pass\n",
    "        return head\n",
    "        pass\n",
    "\n",
    "    def get_num(self, num1, num2):\n",
    "        if num1 <= 1 or num2 <= 1:\n",
    "            return 1\n",
    "        t = [0, 0]\n",
    "        if num1 < num2 :\n",
    "            t[0] = num1\n",
    "            t[1] = num2\n",
    "            pass\n",
    "        else:\n",
    "            t[0] = num2\n",
    "            t[1] = num1\n",
    "            pass\n",
    "        t = tuple(t)\n",
    "        if Solution.cache.__contains__(t) :\n",
    "            return Solution.cache[t]\n",
    "        min_v = t[0]\n",
    "        for v in reversed(range(2, min_v + 1)):\n",
    "            if num1 % v == 0 and num2 % v == 0:\n",
    "                Solution.cache[t] = v\n",
    "                return v\n",
    "            pass\n",
    "        else:\n",
    "            Solution.cache[t] = 1\n",
    "            return 1\n",
    "        pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur.next:\n",
    "            cur.next = ListNode(gcd(cur.val, cur.next.val), cur.next)\n",
    "            cur = cur.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        p=head\n",
    "        while p and p.next:\n",
    "            q=ListNode()\n",
    "            q.val=gcd(p.val,p.next.val)\n",
    "            q.next=p.next\n",
    "            p.next=q\n",
    "            p=p.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head = head._list_node_to_array()\n",
    "        if len(head)==1:return ListNode._array_to_list_node(head)\n",
    "        from math import gcd\n",
    "        ans=[]\n",
    "        for i in range(len(head)-1):\n",
    "            l,r = head[i],head[i+1]\n",
    "            ans.extend([l,gcd(l,r)])\n",
    "            if i==len(head)-2:ans.append(r)\n",
    "        return ListNode._array_to_list_node(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        new_head = ListNode()\n",
    "        current_point = head\n",
    "        new_point = new_head\n",
    " \n",
    "        while current_point:\n",
    "            next_point = current_point.next\n",
    "            new_point.next = ListNode(current_point.val)\n",
    "            new_point = new_point.next\n",
    "            if (next_point):\n",
    "                gcd_value = math.gcd(current_point.val, next_point.val)\n",
    "                new_point.next = ListNode(gcd_value)\n",
    "                new_point = new_point.next\n",
    " \n",
    "            current_point = next_point\n",
    " \n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def gys(self,a,b):\n",
    "        if a >b:\n",
    "            a,b = b, a \n",
    "        res = 1\n",
    "        for i in range(1,a+1):\n",
    "            if a % i == 0 and b % i == 0:\n",
    "                res = i \n",
    "        return res\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        node = head \n",
    "        stack = []\n",
    "        while node:\n",
    "            stack.append(node.val)\n",
    "            node = node.next \n",
    "        new_stack = []\n",
    "        for i in range(len(stack)-1):\n",
    "            new_stack.append(stack[i])\n",
    "            new_stack.append(self.gys(stack[i],stack[i+1]))\n",
    "        new_stack.append(stack[-1])\n",
    "        dummy = ListNode(0)\n",
    "        pre = dummy\n",
    "        for i in new_stack:\n",
    "            cur = ListNode(i)\n",
    "            pre.next = cur \n",
    "            pre = pre.next \n",
    "        return dummy.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        val = []\n",
    "        while cur:\n",
    "            val.append(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        cal = []\n",
    "        cal.append(val[0])\n",
    "        for i in range(1, len(val)):\n",
    "            cal.append(math.gcd(val[i - 1], val[i]))\n",
    "            cal.append(val[i])\n",
    "        print(cal)\n",
    "        \n",
    "        ans = ListNode()\n",
    "        cur = ans;\n",
    "        for v in cal:\n",
    "            cur.next=ListNode(v)\n",
    "            cur=cur.next\n",
    "        return ans.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        arr = []\n",
    "        cur = head\n",
    "        while cur:\n",
    "            arr.append(cur.val)\n",
    "            cur = cur.next\n",
    "        if len(arr) == 1:\n",
    "            return head\n",
    "        res = ListNode(0)\n",
    "        cur = res\n",
    "        for x, y in pairwise(arr):\n",
    "            # print(x, y)\n",
    "            cur.next = ListNode(x)\n",
    "            cur = cur.next\n",
    "            tmp = math.gcd(x, y)\n",
    "            cur.next = ListNode(tmp)\n",
    "            cur = cur.next\n",
    "            # cur.next = ListNode(y)\n",
    "            # cur = cur.next\n",
    "        cur.next = ListNode(arr[-1])\n",
    "        return res.next\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l = []\n",
    "        p = head\n",
    "        while p:\n",
    "            l.append(p.val)\n",
    "            p = p.next\n",
    "        r = []\n",
    "        for i in range(len(l)):\n",
    "            if i == 0:\n",
    "                r.append(l[i])\n",
    "            else:\n",
    "                r.append(math.gcd(l[i], l[i - 1]))\n",
    "                r.append(l[i])\n",
    "        h = ListNode()\n",
    "        p = h\n",
    "        for k in r:\n",
    "            p.next = ListNode(k)\n",
    "            p = p.next\n",
    "        return h.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        h = head\n",
    "        ans = []\n",
    "        while h!=None:\n",
    "            ans.append(h.val)\n",
    "            h = h.next\n",
    "\n",
    "        ret = []\n",
    "        for i in range(len(ans)-1):\n",
    "            a = ans[i]\n",
    "            b = ans[i+1]\n",
    "            \n",
    "            while b != 0:\n",
    "                a, b = b, a % b\n",
    "            ret.append(ans[i])\n",
    "            ret.append(a)\n",
    "        ret.append(ans[-1])\n",
    "\n",
    "        root = ListNode(ret[0])\n",
    "        current = root\n",
    "\n",
    "        # 创建剩余节点\n",
    "        for i in range(1, len(ret)):\n",
    "            current.next = ListNode(ret[i])\n",
    "            current = current.next\n",
    "        \n",
    "        return root\n",
    "\n",
    "            \n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
